package com.lxw.question;

public class Q08 {
    /**
     * 题目描述
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
     * 每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
     * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

     * 链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
     *
     * @param n
     * @return
     */
    //尝试了一个多小时后失败的解答
    public static int cuttingRope2(int n) {
        //剪掉的段数要多，而且长度还不能太短。因此从中间处的前一位开始。
        if(n%2 == 0){
            return startCut(n,0);
        } else{
            return startCut(n,1);
        }
    }

    public static int startCut(int n,int flag){
        if(flag == 0){
            int centerLeft = n / 2 - 1 > 0 ? n / 2 - 1 : 1;
            int result = 1;
            int result1 = 1;
            int topValue = n;
            int div = centerLeft;
            while(topValue != 0){
                if(topValue - div >= 0){
                    result = result * div;
                    topValue = topValue - div;
                } else {
                    div = div - 1;
                }
            }

            topValue = n;
            div = centerLeft;
            boolean isFirst = true;
            while(topValue != 0){
                if(isFirst){
                    result1 = result1 * div;
                    topValue = topValue - div;
                    div = div - 1 > 0 ? div - 1 : 1;
                    isFirst = false;
                } else {
                    if(topValue - div >= 0){
                        result1 = result1 * div;
                        topValue = topValue - div;
                    } else {
                        div = div - 1;
                    }
                }
            }
            return Math.max(result,result1);
        } else{
            int centerLeft = n / 2 + 1;
            int result = 1;
            int result1 = 1;
            int topValue = n;
            int div = centerLeft;
            while(topValue != 0){
                if(topValue - div >= 0){
                    result = result * div;
                    topValue = topValue - div;
                } else {
                    div = div - 1;
                }
            }

            topValue = n;
            div = centerLeft;
            boolean isFirst = true;
            while(topValue != 0){
                if(isFirst){
                    result1 = result1 * div;
                    topValue = topValue - div;
                    div = div - 1;
                    isFirst = false;
                } else {
                    if(topValue - div >= 0){
                        result1 = result1 * div;
                        topValue = topValue - div;
                    } else {
                        div = div - 1;
                    }
                }
            }
            return Math.max(result,result1);
        }

    }


    //看了网友的思路后的题解😞
    public static int cuttingRope(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        int sum = 1;
        //这里之所以设置为4，是为了过滤最后剩一个3和1的情况，因为要把3和1替换为2和2.
        while(n > 4){
            n = n - 3;
            sum = sum * 3;
        }
        return sum * n;
    }

    public static void main(String[] args){
        int result = cuttingRope(9);
        System.out.println(result);
    }
}
